题解 AT5659@洛谷 | 5659@Atcoder 【[AGC040A] ><】

~~看一下这道题的题面,决定放弃这道题,~~突然想起在 Atcoder\text{Atcoder} 上可能会有英文翻译,便到原题看了一眼,真的有。题意大概是:

  • 输入一个仅由 <\lt>\gt 组成的字符串 ss ,假设共 ll 位;
  • 请你构造一个共 l+1l+1 位数列 aa ,满足 ai\sum a_i 最小,同时 aia_iai+1a_{i+1} 的关系是 sis_i 中的字符(即:大于或小于)。
  • 输出 ai\sum a_i

看了一眼数据规模,想到一个 O(n)O(n) 的暴力解法:

  • 从前往后扫一遍字符串,构造 si=<s_i='\lt' 对应的值,具体方法: ai+1=ai+1a_{i+1}=a_i+1 ,可以证明这是最优方案;
  • 从后往前扫一遍字符串,构造 si=>s_i='\gt' 对应的值,具体方法: ai=max(ai,ai+1+1)a_i=\max(a_i, a_{i+1}+1) ,可以证明这是最优方案。

最后再扫一遍记好的数组,记录 ans=aians=\sum a_i ,输出即可,注意 ansans 可能需要使用 long long\text{long long}

代码:

//By: Luogu@rui_er(122461)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

string s;
ll l, a[500001];
ll ans; 

int main()
{
	cin>>s;
	s = " " + s;
	l = s.length() - 1;
	for(int i=1;i<=l;i++) (s[i] == '<') ? (a[i+1] = a[i] + 1) : (a[i+1]);
	for(int i=l;i>=1;i--) (s[i] == '>') ? (a[i] = max(a[i], a[i+1]+1)) : (a[i]);
	for(int i=1;i<=l+1;i++) ans += a[i];
	cout<<ans<<endl;
	return 0;
}